Image decomposition strategies have been used to model and approximate surfaces, pictures, and two dimensional representations, for example. In general, numerous regular shapes are used to “cover” a surface, and each shape can be divided into smaller shapes to more closely approximate the actual surface. The divided shapes, or children of the original shape, can be identified through its relationship to its parent, so that location or coordinates, image density, or other characteristics of the surface can be associated with the parent and child shapes.
Strategies in the past, for example Evans [see, for example, Evans et al., Algorithmica 30(2):264-286 (2001), or Evans, et al., Right Triangular Irregular Networks, Technical Report 97-09, University of Arizona, 1997; Evangelidis et al., The hB11-tree: A multi-attribute index supporting concurrency, recovery and node consolidation, VLDB Journal, 6(1):1-25, 1997], have used a hierarchy of right triangles to decompose a two-dimensional surface, which is given as an array of elevation values. Coordinates are not explicitly stored since they can be calculated from the label (or location code) of the triangle. This is possible because a regular decomposition rule is used, where children are formed by bisecting the parent triangle. A single bit of 0 or 1 indicates the child at each level in the decomposition. Since a pointer-based binary tree structure would be inefficient in its use of space, Evans uses an array where the label of a node determines the node location in the array. To ensure that nodes of different depths have different location codes, Evans prepends a 1 to the node label. In general, there is a one-to-one mapping between sequential integers and location codes with depth information. Evans chooses to work with a continuous sequence of integer values instead of using depth explicitly. Evans finds neighbors using recurrence relations and recursive algorithms, which run in an amount of time proportional to the length of the location code (i.e., proportional to the depth of the triangle). Evans also stores three extra bits with each triangle to indicate the size of the neighboring triangles in each of the three possible directions.
Kaufman [see, for example, Zhou, Chen, and Arie E. Kaufman: Multiresolution tetrahedral framework for visualizing regular volume data, IEEE Visualization 1997: 135-142; and Dachille, Mueller, and Arie E. Kaufman: Volumetric backprojection, Volviz 2000: 109-117] presents a multiresolution tetrahedral framework. The basic element of the decomposition is a tetrahedron bisected along its longest edge, generating the next level of shapes. The initial space is a cube divided into twelve tetrahedra after adding only the center point of the cube. Next, the recursive subdivision process adds the midpoint of an edge of a tetrahedron, and that tetrahedron is bisected into two by the plane passing through the added point and the opposite edge. Regardless of the number of times the tetrahedra are bisected, the resulting shapes always fall into one of three cases. The appearance of successive shapes is actually cyclic, in that every three levels of decomposition result in a geometrically similar shape. Since the subdivision can be represented by a full binary tree, it is simply stored in an array. Using this strategy, the addresses (or location code) of children and parents are easy to obtain with simple calculations, which are the same for any binary tree.
Hebert [see, for example, D. J. Hebert, Symbolic local refinement of tetrahedral grids, Journal of Symbolic Computation, 17(5):457-472, 1994] introduces the idea of using symbolic algorithms to find parents, children, and neighbors. Operations are done within symbolic tetrahedral codes, which contain a path to the lattice origin of the tetrahedron and a triple (permutation number, rotation number, and descendent number) identifying the tetrahedron relative to the lattice origin. These lattice origins effectively indicate the cubes (or sub-cubes) containing a given tetrahedron. In particular, the center of each cube is used to represent the cube and acts as the reference point for locating tetrahedra. Using this technique, three of the four tetrahedra sharing a face will share the same lattice origin (center of cube) and will require only a table lookup to retrieve the symbolic code of the appropriate neighbor. For the fourth tetrahedron along the remaining face, the path to the lattice origin must be updated to get the complete symbolic code of the neighbor.
The limitations in each of these approaches include computer processing requirements, inability to provide real time manipulation of 3D images from PC platforms, and inability to process and manipulate complex images efficiently and/or in real time.